package leetCode.offer14_i;

/**
 * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），
 * 每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？
 *
 * 例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
 *
 * 示例 1：
 * 输入: 2
 * 输出: 1
 * 解释: 2 = 1 + 1, 1 × 1 = 1
 *
 * 示例2:
 * 输入: 10
 * 输出: 36
 * 解释: 10 = 3 + 3 + 4, 3 ×3 ×4 = 36
 *
 * 提示：
 * 2 <= n <= 58
 */
public class Solution1 implements Solution{


    /**
     * 解法：对这个题目，我们可以先采用举例法看看有什么规律
     * 定义f(n) 就是n的最大乘积
     * f(1) = 0
     * f(2) = 1
     * f(3) = 1*2 = 2

     * g(2) = 2
     * g(3) = 3
     * f(4) = 2*2 = 4 = g(2)*g(2)  g(4) = 4
     * f(5) = 2*3 = 6 = g(2)*g(3)  g(5) = 6
     * f(6) = 3*3 = 9 = g(3)*g(3)
     * f(7) = 2*2*3 = 12 = g(3)*g(4)
     * @param n
     * @return
     */
    @Override
    public int cuttingRope(int n) {
        if(n<2) return 0;
        if(n==2) return 1;
        if(n==3) return 2;

        int[] tem = new int[n+1];
        tem[1] = 1;
        tem[2] = 2;
        tem[3] = 3;
        int max ;
        for(int i=4;i<n+1;i++){
            max = 0;
            for(int j=1;j<=i/2;j++) {
                int mul = tem[j] * tem[i-j];
                if(max < mul){
                    max = mul;
                }
                tem[i] = max;
            }
        }
        return tem[n];
    }

    public static void main(String[] args) {
        Solution1 solution1 = new Solution1();
        System.out.println(solution1.cuttingRope(7));
    }


}
